The world financial crisis is quite a
subject. Some people are more relaxed while others are quite anxious. John is
one of them. He is very concerned about the evolution of the stock exchange. He
follows stock prices every day looking for rising trends. Given a sequence of
numbers p1, p2, ..., pn representing stock prices, a rising trend is a subsequence pi1 < pi2 < ... < pik, with i1 < i2 < ... < ik.
John’s problem is to find very quickly the longest rising trend.
Input. Each
data set in the file stands for a particular set of stock prices. A data set
starts with the length l (l ≤ 105)
of the sequence of numbers, followed by the numbers (a number fits a long
integer).
White
spaces can occur freely in the input. The input data are correct and terminate
with an end of file.
Output. The
program prints the length of the longest rising trend.
For each
set of data the program prints the result to the standard output from the
beginning of a line.
|
Sample input |
Sample output |
|
6
5
2 1 4 5 3 3 1
1 1 4
4
3 2 1 |
3 1 1 |
longest
increasing subsequence
Consists
of several test cases. Each
test contains a sequence of numbers for which the length of the longest
increasing subsequence (LIS) must be
found.
Declare the array lis.
#define MAX 100001
int lis[MAX];
The
main part of the program. Read and process the input sequence.
while (scanf("%d",&n) == 1)
{
for (len = i = 0; i < n; i++)
{
scanf("%d",&element);
pos =
lower_bound(lis,lis+len,element) - lis;
if (pos < len) lis[pos] = element; else lis[len++] = element;
}
Print the length of LIS.
printf("%d\n",len);
}
Java realization
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int lis[] = new int[100001];
while (con.hasNextInt())
{
int n = con.nextInt();
int len = 0;
for (int i = 0; i < n; i++)
{
int element = con.nextInt();
int pos = Arrays.binarySearch(lis, 0, len, element);
if(pos < 0) pos = - (pos + 1);
lis[pos] = element;
if(pos == len) len++;
}
System.out.println(len);
}
con.close();
}
}